package com.lw.leetcode.stack.c;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 2334. 元素值大于变化阈值的子数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/18 9:10
 */
public class ValidSubarraySize {

    public static void main(String[] args) {
        ValidSubarraySize test = new ValidSubarraySize();

        // 3
        int[] arr = {1, 3, 4, 3, 1};
        int threshold = 6;

        // 1 / 2 / 3 / 4/ 5
//        int[] arr = {6, 5, 6, 5, 8};
//        int threshold = 24;

        int i = test.validSubarraySize(arr, threshold);
        System.out.println(i);
    }

    public int validSubarraySize(int[] nums, int threshold) {
        int length = nums.length;
        Stack<Long> stack = new Stack<>();
        stack.add(-1L);
        for (int i = 0; i < length; i++) {
            long num = nums[i];
            Long peek = stack.peek();
            long a = peek >> 32;
            if (a >= num) {
                int index = peek.intValue();
                while (a >= num) {
                    stack.pop();
                    peek = stack.peek();
                    int v = a == num ? i - peek.intValue() : index - peek.intValue();
                    if (a * v > threshold) {
                        return v;
                    }
                    a = peek >> 32;
                }
            }
            stack.add((num << 32) + i);
        }
        int index = stack.peek().intValue();
        while (stack.size() > 1) {
            long a = stack.pop() >> 32;
            int v = index - stack.peek().intValue();
            if (a * v > threshold) {
                return v;
            }
        }
        return -1;
    }

}
